/*
 * @Author: long-xinyu2 2192763423@qq.com
 * @Date: 2025-06-08 17:45:35
 * @LastEditors: long-xinyu2 2192763423@qq.com
 * @LastEditTime: 2025-06-08 17:47:00
 * @FilePath: \algorithm-training\leetcode\1326. 灌溉花园的最少水龙头数目.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @Author: long-xinyu2 2192763423@qq.com
 * @Date: 2025-06-08 17:45:35
 * @LastEditors: long-xinyu2 2192763423@qq.com
 * @LastEditTime: 2025-06-08 17:45:54
 * @FilePath: \algorithm-training\leetcode\1326. 灌溉花园的最少水龙头数目.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<pair<int,int>>p;
        for(int i = 0; i <= n; i ++)
        {
            int ll = i - ranges[i];
            int rr = i + ranges[i];
            if(ll < 0) ll = 0;
            if(rr > n) rr = n;
            p.push_back({ll,rr});
        }   
        sort(p.begin(),p.end());
        int ans = 0;
        int start = 0;
        int right = 0;
        for(int i = 0; i <= n;i ++)
        {
            int flag = 0;
            while(i <= n && p[i].first <= start)
            {
                flag = 1;
                right = max(right,p[i].second);
                i ++;
            }
            i --;
            if(flag == 1)
            {
                ans ++;
                start = right;
            }
            if(flag == 0)
            {
                return -1;
            }
            if(right == n)
            {
                break;
            }
        }
        return ans;
    }
};